<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>The Worst Case</title>
<link rel="stylesheet" href="../../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../../index.html" title="Boost.Sort">
<link rel="up" href="../pdqsort.html" title="2.2.- pdqsort">
<link rel="prev" href="pdqsort_avg.html" title="The Average Case">
<link rel="next" href="pdqsort_bad_partitions.html" title="Bad Partitions">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="pdqsort_avg.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../pdqsort.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="pdqsort_bad_partitions.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="sort.single_thread.pdqsort.pdqsort_worst"></a><a class="link" href="pdqsort_worst.html" title="The Worst Case">The Worst
        Case</a>
</h4></div></div></div>
<p>
          Quicksort naturally performs bad on inputs that form patterns, due to it
          being a partition-based sort. Choosing a bad pivot will result in many
          comparisons that give little to no progress in the sorting process. If
          the pattern does not get broken up, this can happen many times in a row.
          Worse, real world data is filled with these patterns.
        </p>
<p>
          Traditionally the solution to this is to randomize the pivot selection
          of quicksort. While this technically still allows for a quadratic worst
          case, the chances of it happening are astronomically small. Later, in introsort,
          pivot selection is kept deterministic, instead switching to the guaranteed
          O(n log n) heapsort if the recursion depth becomes too big. In <code class="literal"><code class="computeroutput">pdqsort</code></code> we adopt a
          hybrid approach, (deterministically) shuffling some elements to break up
          patterns when we encounter a "bad" partition. If we encounter
          too many "bad" partitions we switch to heapsort.
        </p>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2014-2017 Steven
      Ross, Francisco Tapia, Orson Peters<p>
        Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
        Software License, Version 1.0</a>.
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="pdqsort_avg.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../pdqsort.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="pdqsort_bad_partitions.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
